// DeflaterHuffman.cs
//
// Copyright (C) 2001 Mike Krueger
// Copyright (C) 2004 John Reilly
// Copyright (C) 2010 Thomas Maierhofer
//
// (2010) This Code was modified from SharpZipLib http://www.icsharpcode.net/OpenSource/SharpZipLib/  
// to fit the needs of Second WAF - a heavy load web application framework 
//
// This file was translated from java, it was part of the GNU Classpath
// Copyright (C) 2001 Free Software Foundation, Inc.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
// Linking this library statically or dynamically with other modules is
// making a combined work based on this library.  Thus, the terms and
// conditions of the GNU General Public License cover the whole
// combination.
// 
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent
// modules, and to copy and distribute the resulting executable under
// terms of your choice, provided that you also meet, for each linked
// independent module, the terms and conditions of the license of that
// module.  An independent module is a module which is not derived from
// or based on this library.  If you modify this library, you may extend
// this exception to your version of the library, but you are not
// obligated to do so.  If you do not wish to do so, delete this
// exception statement from your version.

namespace WAF.Content
{
    using System;

    public partial class Deflater
    {
        HuffmanTree literalTree;
        HuffmanTree distanceTree;
        HuffmanTree bitLengthTree;

        // Buffer for distances

        short[] distanceBuffer;
        byte[] literalBuffer;

        int lastLiteral;
        int extraBits;

        /// <summary>
        /// Resets the Huffman encoder
        /// </summary>		
        void HuffmanReset()
        {
            lastLiteral = 0;
            extraBits = 0;
            literalTree.Reset();
            distanceTree.Reset();
            bitLengthTree.Reset();
        }
        
        /// <summary>
        /// Write all trees to pending buffer
        /// </summary>
        /// <param name="blTreeCodes">The number/rank of treecodes to send.</param>
        void SendAllTrees(int blTreeCodes)
        {
            bitLengthTree.BuildCodes();
            literalTree.BuildCodes();
            distanceTree.BuildCodes();
            OutputBufferWriteBits(literalTree.numCodes - 257, 5);
            OutputBufferWriteBits(distanceTree.numCodes - 1, 5);
            OutputBufferWriteBits((uint)(blTreeCodes - 4), 4);
            for (int rank = 0; rank < blTreeCodes; rank++)
            {
                OutputBufferWriteBits(bitLengthTree.symbols[BL_ORDER[rank]].Bits, 3);
            }
            literalTree.WriteTree(bitLengthTree);
            distanceTree.WriteTree(bitLengthTree);

        }

        /// <summary>
        /// Compress current buffer writing data to outputBuffer buffer
        /// </summary>
        void CompressBlock()
        {
            HuffmanTree.Symbol[] literalTreeSymbols = literalTree.symbols;
            HuffmanTree.Symbol[] distanceTreeSymbols = distanceTree.symbols;
            const int bufferSize = 128;
            HuffmanTree.Symbol[] symbolWriteBuffer = new HuffmanTree.Symbol[bufferSize];
            int symbolWriteBufferIndex = 0;

            for (int i = 0; i < this.lastLiteral; i++)
            {
                int dist = distanceBuffer[i];
                uint litlen = literalBuffer[i];
                if (dist-- != 0)
                {
                    // int lengthCode = LengthCode((int)litlen);

                    BlockLengthCodes blockLengthCode = staticBlockLengthCodes[litlen];
                    symbolWriteBuffer[symbolWriteBufferIndex++] = literalTreeSymbols[blockLengthCode.LengthCode];
                    // OutputBufferWriteSymbol(literalTreeSymbols, lengthCode);
                    // literalTree.WriteSymbol(lengthCode);

                    // int bits = (lengthCode - 261) / 4;
                    // if (bits > 0 && bits <= 5)
                    if (blockLengthCode.ExtraBits > 0)
                    {
                        /*
                        symbol.BitsCode = (ushort)(litlen & ((1 << bits) - 1));
                        symbol.BitsLength = (ushort) bits;
                        OutputBufferWriteSymbol(symbol;
                        */
                        // OutputBufferWriteBits((uint)(litlen & ((1 << bits) - 1)), bits);

                        // symbolWriteBuffer[symbolWriteBufferIndex].BitsCode = (ushort)(litlen & ((1 << (litlenPrecalc.Bits)) - 1));
                        symbolWriteBuffer[symbolWriteBufferIndex].BitsCode = blockLengthCode.ExtraBitsCode;
                        symbolWriteBuffer[symbolWriteBufferIndex++].Bits = blockLengthCode.ExtraBits; 


                    }

                    BlockDistanceCodes blockDistanceCode = staticBlockDistanceCodes[dist];
                    // int distanceCode = DistanceCode(dist);
                    // OutputBufferWriteSymbol(distanceTreeSymbols, distanceCode);
                    symbolWriteBuffer[symbolWriteBufferIndex++] = distanceTreeSymbols[blockDistanceCode.DistanceCode];

                    // distanceTree.WriteSymbol(distanceCode);

                    // int bits = distanceCode / 2 - 1;
                    if (blockDistanceCode.ExtraBits > 0)
                    {
                        symbolWriteBuffer[symbolWriteBufferIndex].BitsCode = blockDistanceCode.ExtraBitsCode;
                        symbolWriteBuffer[symbolWriteBufferIndex++].Bits = blockDistanceCode.ExtraBits;
                        // OutputBufferWriteBits((uint)(dist & ((1 << bits) - 1)), bits);
                    }
                }
                else
                {
                    symbolWriteBuffer[symbolWriteBufferIndex++] = literalTreeSymbols[litlen];
                    // OutputBufferWriteSymbol(literalTreeSymbols,(int) litlen);
                    // literalTree.WriteSymbol((int)litlen);
                }
                if (symbolWriteBufferIndex + 3 >= symbolWriteBuffer.Length)
                {
                    OutputBufferWriteSymbol(symbolWriteBuffer, symbolWriteBufferIndex);
                    symbolWriteBufferIndex = 0;
                }
            }

 
            OutputBufferWriteSymbol(symbolWriteBuffer, symbolWriteBufferIndex);

            literalTree.WriteSymbol(EOF_SYMBOL);

        }

        /// <summary>
        /// Flush block to output with no compression
        /// </summary>
        /// <param name="stored">Data to write</param>
        /// <param name="storedOffset">Index of first byte to write</param>
        /// <param name="storedLength">Count of bytes to write</param>
        /// <param name="lastBlock">True if this is the last block</param>
        void FlushStoredBlock(int storedOffset, int storedLength, bool lastBlock)
        {
            OutputBufferWriteBits((ulong)((STORED_BLOCK << 1) + (lastBlock ? 1 : 0)), 3);
            OutputBufferAlignToByte();
            OutputBufferWriteShortLSBFirst((uint) storedLength);
            OutputBufferWriteShortLSBFirst((uint) ~storedLength);
            OutputBufferWriteBlock(window, storedOffset, storedLength);
            HuffmanReset();
        }

        /// <summary>
        /// Flush block to output with compression
        /// </summary>		
        /// <param name="stored">Data to flush</param>
        /// <param name="storedOffset">Index of first byte to flush</param>
        /// <param name="storedLength">Count of bytes to flush</param>
        /// <param name="lastBlock">True if this is the last block</param>
        void FlushBlock(int storedOffset, int storedLength, bool lastBlock)
        {
            literalTree.frequencies[EOF_SYMBOL]++;

            // Build trees
            literalTree.BuildTree();
            distanceTree.BuildTree();

            // Calculate bitlen frequency
            literalTree.CalcBLFreq(bitLengthTree);
            distanceTree.CalcBLFreq(bitLengthTree);

            // Build bitlen tree
            bitLengthTree.BuildTree();

            int blTreeCodes = 4;
            for (int i = 18; i > blTreeCodes; i--)
            {
                if (bitLengthTree.symbols[BL_ORDER[i]].Bits > 0)
                {
                    blTreeCodes = i + 1;
                }
            }
            int opt_len = 14 + blTreeCodes * 3 + bitLengthTree.GetEncodedLength() +
                literalTree.GetEncodedLength() + distanceTree.GetEncodedLength() +
                extraBits;

            int static_len = extraBits;
            for (int i = 0; i < STATIC_LITERAL_CODES_NUMBER; i++)
            {
                static_len += literalTree.frequencies[i] * staticLiteralSymbols[i].Bits;
            }
            for (int i = 0; i < STATIC_DISTANCE_CODES_NUMBER; i++)
            {
                static_len += distanceTree.frequencies[i] * staticDistanceSymbols[i].Bits;
            }
            if (opt_len >= static_len)
            {
                // Force static trees
                opt_len = static_len;
            }

            if (storedOffset >= 0 && storedLength + 4 < opt_len >> 3)
            {
                // Store Block

                //				if (DeflaterConstants.DEBUGGING) {
                //					//Console.WriteLine("Storing, since " + storedLength + " < " + opt_len
                //					                  + " <= " + static_len);
                //				}
                FlushStoredBlock(storedOffset, storedLength, lastBlock);
            }
            else if (opt_len == static_len)
            {
                // Encode with static tree
                OutputBufferWriteBits((ulong)((STATIC_TREES << 1) + (lastBlock ? 1 : 0)), 3);
                literalTree.SetStaticCodes(staticLiteralSymbols);
                distanceTree.SetStaticCodes(staticDistanceSymbols);
                CompressBlock();
                HuffmanReset();
            }
            else
            {
                // Encode with dynamic tree
                OutputBufferWriteBits((ulong)((DYN_TREES << 1) + (lastBlock ? 1 : 0)), 3);
                SendAllTrees(blTreeCodes);
                CompressBlock();
                HuffmanReset();
            }
        }

        /// <summary>
        /// Get value indicating if internal buffer is full
        /// </summary>
        /// <returns>true if buffer is full</returns>
        bool IsFull()
        {
            return lastLiteral >= BUFSIZE;
        }

        /// <summary>
        /// Add literal to buffer
        /// </summary>
        /// <param name="literal">Literal value to add to buffer.</param>
        /// <returns>Value indicating internal buffer is full</returns>
        bool AddLiteral(int literal)
        {
            distanceBuffer[lastLiteral] = 0;
            literalBuffer[lastLiteral++] = (byte)literal;
            literalTree.frequencies[literal]++;
            return IsFull();
        }

        /// <summary>
        /// Add distance code and length to literal and distance trees
        /// </summary>
        /// <param name="distance">Distance code</param>
        /// <param name="length">Length</param>
        /// <returns>Value indicating if internal buffer is full</returns>
        bool AddDistance(int distance, int length)
        {
            length -= 3;

            distanceBuffer[lastLiteral] = (short) distance;
            literalBuffer[lastLiteral++] = (byte)(length);

            BlockDistanceCodes blockDistanceCode = staticBlockDistanceCodes[distance - 1]; 
            BlockLengthCodes blockLengthCode = staticBlockLengthCodes[length];

            literalTree.frequencies[blockLengthCode.LengthCode]++;
            extraBits += blockLengthCode.ExtraBits;

            
            distanceTree.frequencies[blockDistanceCode.DistanceCode]++;
            extraBits += blockDistanceCode.ExtraBits;
            return IsFull();
        }


        /// <summary>
        /// Reverse the bits of a 16 bit value.
        /// </summary>
        /// <param name="toReverse">Value to reverse bits</param>
        /// <returns>Value with bits reversed</returns>
        static ushort BitReverse(uint toReverse)
        {
            return (ushort)(nibbleReverse[toReverse & 0xF] << 12 |
                            nibbleReverse[(toReverse >> 4) & 0xF] << 8 |
                            nibbleReverse[(toReverse >> 8) & 0xF] << 4 |
                            nibbleReverse[toReverse >> 12]);
        }

    }
}
